#include "my_malloc.h"
#include "math.h"

/* You *MUST* use this macro when calling my_sbrk to allocate the 
 * appropriate size. Failure to do so may result in an incorrect
 * grading!
 */
#define SBRK_SIZE 2048

/* If you want to use debugging printouts, it is HIGHLY recommended
 * to use this macro or something similar. If you produce output from
 * your code then you will receive a 20 point deduction. You have been
 * warned.
 */
#ifdef DEBUG
#define DEBUG_PRINT(x) printf x
#else
#define DEBUG_PRINT(x)
#endif


/* make sure this always points to the beginning of your current
 * heap space! if it does not, then the grader will not be able
 * to run correctly and you will receive 0 credit. remember that
 * only the _first_ call to my_malloc() returns the beginning of
 * the heap. sequential calls will return a pointer to the newly
 * added space!
 * Technically this should be declared static because we do not
 * want any program outside of this file to be able to access it
 * however, DO NOT CHANGE the way this variable is declared or
 * it will break the autograder.
 */
void* heap;
int heap_size = 0;


/* our freelist structure - this is where the current freelist of
 * blocks will be maintained. failure to maintain the list inside
 * of this structure will result in no credit, as the grader will
 * expect it to be maintained here.
 * Technically this should be declared static for the same reasons
 * as above, but DO NOT CHANGE the way this structure is declared
 * or it will break the autograder.
 */
metadata_t* freelist[8];
/**** SIZES FOR THE FREE LIST ****
 * freelist[0] -> 16
 * freelist[1] -> 32
 * freelist[2] -> 64
 * freelist[3] -> 128
 * freelist[4] -> 256
 * freelist[5] -> 512
 * freelist[6] -> 1024
 * freelist[7] -> 2048
 */


void* my_malloc(size_t size)
{
	size_t size_total = size + sizeof(metadata_t);
	int heap_int = (size_t)heap;
	int arr_idx;
	/* stores the return value */ 
	metadata_t * metadata_ptr = NULL; 
	printf("ENTERED SIZE: %d\n",size);
	printf("METADATA SIZE: %d\n",sizeof(metadata_t));	
	if(size_total > SBRK_SIZE || size_total < 0) {
		ERRNO = SINGLE_REQUEST_TOO_LARGE; 
  		return NULL;
		printf("INVALID REQUEST\n");
	}
	else {
		if(!heap || heap_int+heap_size+size_total > SBRK_SIZE){
			metadata_t* new_heap = my_sbrk(SBRK_SIZE); 
			/* set up new heap */
			if (!heap)
				heap = new_heap;
			new_heap->next = freelist[7];
			freelist[7] = (metadata_t*) heap;
			freelist[7]->prev = freelist[7]->next = NULL;
			freelist[7]->in_use = 0;
			freelist[7]->size = SBRK_SIZE;
			heap_size+=sizeof(metadata_t);
		}
	}
		/* 
		int slot = 16;
		while(slot <= SBRK_SIZE) {
			if(size_total < slot) {
					size_total = slot;
					break;
			}
			else if(size_total > slot) { //added for readability
				slot*=2; //doubles the size, should I do a bit shift here?
			}
		}
		*/
	size_total = 2 << ((int)ceil(log2(size_total)) - 1);
	printf("SIZE TOTAL: %d\n", size_total);
	DEBUG_PRINT(size_total);
	arr_idx = (int)log2(size_total) - 4;
	printf("START INDEX: %d\n", arr_idx);
	DEBUG_PRINT(arr_idx);
	find_mem(arr_idx,size_total, metadata_ptr);
	return (char*)(metadata_ptr + sizeof(metadata_t)); 
}
/*
This function is used to dynamically allocate entire arrays at a time. It takes in the number of elements to be
allocated in the array as well as the size of each element. It will use malloc to allocate a stretch of dynamic
memory appropriately sized for the user. Note that calloc also initializes this stretch of memory to 0.
Should the malloc call fail, it should return NULL and set the proper error code.
*/

void* my_calloc(size_t num, size_t size)
{
	char* addr = my_malloc(size*num);
	if(!addr) {
		ERRNO = OUT_OF_MEMORY;	
		printf("NO MEMORY AVAILABLE\n");
  		return NULL;
	} else {
		/* Copy 0 to the first num characters of addr. Return addr*/
  		size_t i;
  		for (i = 0; i < num; i++, addr++) {
  	  		*addr = 0;
  		}
	}
  return (metadata_t*)addr;
}

void my_free(void* ptr) 
{ 	
	int p_cast = (int)ptr;	
	metadata_t* pointer = (metadata_t*)(p_cast - sizeof(metadata_t)); /* THIS LINE (char)*/
	int restore_heap = pointer->size;
	/*enlarge the ptr by multiplying the size by two and removing the one next to it if it's the same size
	takes the pointer and checks to see if it has a buddy, if it does, try to combine them*/
	int arr_idx;
	metadata_t* buddy = get_buddy(pointer);
	while(buddy_is_free(pointer,buddy)) {
			arr_idx = (int)log2(pointer->size) - 4;
			if(buddy) { /*buddy is free, so I need to remove it*/
				if(!remove_target(freelist[arr_idx], buddy)) {
					printf("remove target failed\n");
					/*this should never be called.*/
				}
			}
			pointer->size*=2; 
			pointer->in_use = 0;
			buddy = get_buddy(pointer);
			/*remove buddy from freelist (in get buddy, remove the one in freelist)*/
	}	
	heap_size-=restore_heap; /*deallocate memory?*/
	/*add pointer to the freelist*/
	arr_idx = (int)log2(pointer->size) - 4;
	freelist[arr_idx]= pointer; 
}
/*
This function takes in two pointers, a source and a destination as well as a size_t that indicates the number of
bytes to be copied. The source and destination could overlap, so it is important to copy as if you copied all the
number of bytes to be copied from the source to a temporary buffer and then copied to the destination. 
*/
void* my_memmove(void* dest, const void* src, size_t num_bytes)
{
	unsigned char *dest_ptr = dest;
	const unsigned char *src_ptr = src;
	if(src_ptr!=dest) { /*if they are already equal, then just return*/
		/*<-----s-----> <-----d----->  start at end of s*/
		if((src_ptr+num_bytes) < dest_ptr) {
			for (dest_ptr += num_bytes, src_ptr += num_bytes; num_bytes--;){
      			*--dest_ptr = *--src_ptr;
			}
		/*<-----s--<==>--d----->       start at end of s*/
		} else if((src_ptr+num_bytes) > dest_ptr && (src_ptr+num_bytes) < (dest_ptr+num_bytes)){
  		for (dest_ptr += num_bytes, src_ptr += num_bytes; num_bytes--;){
      			*--dest_ptr = *--src_ptr;
			}
		/*<-----d--<==>--s----->       start at beginning of s*/
		} else if(src_ptr < (dest_ptr+num_bytes) && (src_ptr+num_bytes) > (dest_ptr+num_bytes)){
			while(num_bytes--) {
      			*dest_ptr++ = *src_ptr++;
			}
		/*<-----d-----> <-----s----->  start at beginning of s*/
		} else if(dest_ptr+num_bytes < src_ptr) {
			while(num_bytes--) {
      			*dest_ptr++ = *src_ptr++;
			}
		}
	}
  return dest;
}
/*
	finds memory for malloc
*/
int find_mem(int arr_idx, int goal_size, metadata_t* ret) {
	metadata_t *head = freelist[arr_idx]; 
	metadata_t *first;
	metadata_t *second;
	if (head && head->size == goal_size) {
		/* found */
		ret = head;
		remove_front(ret, arr_idx);
		ret->in_use = 1;
		DEBUG_PRINT("FOUND\n");
		printf("found:%d\n",(int)ret);
		return 1;
	} else if (head && head->size > goal_size) {
		/* split */
		remove_front(head, arr_idx);
		/*remove_front(ret, arr_idx);*/
		/*first = (metadata_t*) (heap+heap_size);*/		/*allocate*/
		/*heap_size+=sizeof(metadata_t);*/
		first = head;
		first->size = head->size >> 1;
		heap_size+=first->size;
		second = (metadata_t*) ((int)heap+heap_size);	/* allocate*/
		/*heap_size+=sizeof(metadata_t);*/
		second->size = first->size;
		/*heap_size+=second->size;*/
		first->in_use = second->in_use = 0;
		first->next = second;
		first->prev = NULL;
		second->prev = first;
		second->next = freelist[arr_idx-1]; 
		freelist[arr_idx-1] = first;				
		/*heapsize-=sizeof(metadata_t);// de-allocate*/
		printf("running again, index: %d\n", arr_idx);
		return find_mem(arr_idx-1, goal_size, ret);
	} else if (arr_idx < 8) {
		/* go up a level*/
		printf("up a level: %d\n",arr_idx);
		return find_mem(arr_idx+1, goal_size, ret);
	}
	return 0; /* it failed */
}
/*
	determines if blockA and blockB are buddys, 
	if so, it makes blockA point to the left buddy and blockB point to the right one
	else it returns false
	-used with my_free(void*)
*/
int buddy_is_free(metadata_t* blockA, metadata_t* blockB) {
	int a_ptr = (int)blockA;
	int b_ptr = (int)blockB;
	int result;
	int n = (int)log2(blockA->size);
	if(!blockA || !blockB) /* if either is null, return false */
		return 0;
	/* delete enlarge and keep doing that, 
	then look at the size to see what array it needs to be put in */
	/* editing addresses for calculations */
	a_ptr -= (int)heap; 
	b_ptr -= (int)heap; 
	/* bits match in n+1 position */
	result = (a_ptr & 1<<(n+1))&(b_ptr & 1<<(n+1)); 
	/* to determine the starting address */
	if(result && !blockB->in_use){
		if(!(b_ptr & (1<<n))) {
			/*if blockB is starting, swaps the positions of the two*/
			metadata_t* temp = blockB;
			blockB = blockA;
			blockA = temp;
		}
		else { /*if (!(a_ptr & (1<<n)))*/
			/*blockA is starting*/
		}
	} 
	return result;
}

/*
	gets block's buddy, if it is not in use
	otherwise returns NULL
*/
void* get_buddy(metadata_t* block) {
	int a_ptr;
	int buddy_ptr;
	int n = (int)log2(block->size);
	/*int b_ptr;
	int p_cast = (int)block;
	int result;*/
	metadata_t* buddy;/* = (metadata_t*)(p_cast+ (char)block->size);
	b_ptr = (int)buddy;*/
	a_ptr = (int)block;
	buddy_ptr = a_ptr ^ (1UL << n); /*flips the n bit to get the buddy*/
	buddy = (metadata_t*)buddy_ptr;

	/*a_ptr-= (int)heap;
	b_ptr-= (int)heap; */
	/*result = (a_ptr & 1<<(n+1))&(b_ptr & 1<<(n+1));*/
	if(buddy->in_use || buddy->size != block->size)
		return NULL;
	else 
		return buddy;
}

/*================================

	LINKED LIST IMPLEMENTATION

==================================*/
/*
 removes a node to the front of the freelist
 return: whether or not it was sucessful
*/
int remove_front(metadata_t* head, int arr_idx) {
	if(!head) {
		return 0; /*already empty*/
	}
	else if(!head->next) { /* one element list */
		freelist[arr_idx] = 0;
		return 1;
	}
	else {
		freelist[arr_idx] = head->next;
		freelist[arr_idx]->prev = NULL;
		return 1;
	}
}

/*
	removes a node to the back of the freelist
	return: whether or not it was sucessful
*/
int remove_back(metadata_t* head) {
	if(!head) {
		return 0;
	}	
	else if(!head->next) { /* one element list */
			int arr_idx = (int)log2(head->size) - 4;
			freelist[arr_idx] = 0;
			return 1;
	}
	else {
		metadata_t* curr = head;
		while(curr->next->next) {
			curr = curr->next;
		}
		curr->next->prev = NULL;
		curr->next = NULL;
		return 2;
	}
}	
/*
	removes the target node from a list, 
	and returns 0 if it didn't find it or failed
*/
int remove_target(metadata_t* head, metadata_t* target) {
	if(!head) {
		return 0;
	}	
	else if(!head->next) { /* one element list */
		int arr_idx = (int)log(head->size) - 4;
		freelist[arr_idx] = 0;
		return 1;
	}
	else if(head==target) {
		int arr_idx = (int)log(head->size) - 4;
		remove_front(head, arr_idx);
		return 1;
	}
	else {
		metadata_t* curr = head;
		while(curr->next) {
			curr = curr->next;
			if(curr->next==target) {
				curr->next = curr->next->next;
				curr->next->prev = curr;
				return 1;
			}
		}
		return 0; /* one element list */
	}
}	

/*
	adds a node to the front of the freelist
	return: whether or not it was sucessful
*/
int push_front(metadata_t* newdata, int arr_idx) {
	if(arr_idx < 0 || arr_idx > 7) 
		return 0;
	else if(!newdata) 
		return 0;
	else if(!freelist[arr_idx]) { /* empty list */
		freelist[arr_idx] = newdata;
		return 1;
	} else {
		freelist[arr_idx]->prev = newdata;
		newdata->next = freelist[arr_idx];
		freelist[arr_idx] = newdata;
		return 2;
	}

}

/*
	adds a node to the back of the freelist
	return: whether or not it was sucessful
*/
int push_back(metadata_t* newdata, int arr_idx) {
	if(arr_idx < 0 || arr_idx > 7) 
		return 0;
	else if(!newdata) 
		return 0;
	else {
		metadata_t* curr = freelist[arr_idx];
		while(curr->next) {
			curr = curr->next;
		}
		curr->next = newdata;
		newdata->prev = curr;
		return 1;
	}
}

double log2(double n) {
   return log(n) / log(2);
}
